1. Field of the Invention
The present invention applies to the field of data coding and, in particular, to an error-correcting decoder.
2. Description of the Prior Art
Digital devices, such as computers and various digital communications equipment, store and process data as binary digits, also known as bits. A bit is either zero or one (“0” or “1”). All digital information, such as mp3 files, jpeg images, text files, DVD movies, and so on are stored as a collection of bits. When bits are transferred over a communication medium, errors may be introduced so that the bits received are not identical to the original bits. To ensure the accuracy of received data, various error detection and correction devices have been developed, such as, e.g., parity check codes, checksums, block codes, and cyclic redundancy checks.
Parity check codes are well known. A parity check code adds a single parity bit to a block of data bits so that the number of “1” bits is even. Odd parity checking works in the same manner, except the number of “1” bits is made to be odd. For example, over the block “0011010110” the parity bit added would be “1,” because there are five “1s” in the block, which is an odd number, and one more “1” makes it even.
Block codes, such as Hamming codes, are also well known. An error correcting block generates a codeword using a block of data bits. The codewords contain enough redundancy to be used to correct a predetermined number of bit errors, the number depending on the amount of redundancy. Block codes are based on the principle that if allowed codewords are kept a minimum distance from each other, errors can be corrected. For example, allowed Hamming codewords are three bit differences apart from all other Hamming codewords. Thus, the Hamming code can correct one error. Codes can be developed to correct any number of errors.
Block codes can either be used to correct errors or to detect them. A block code can generally detect a larger number of errors than it can correct. For example, the Hamming code can detect two errors. An extended block code encodes a block of data using both a block encoder and a single parity check code. An advantage of this is that the extended block code can sometimes detect one more error than the block code can detect. For example, a Hamming code can detect two errors and an extended Hamming code can detect three errors. However, both the Hamming code and the extended Hamming code can only be used to correct one error. Traditional decoding of extended codewords does not increase the error correction capabilities of the block code. The extended block code cannot be used to correct more errors than the block code alone.